package Hot100;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2021-12-20 14:26
 */
public class letterCombinations17 {

    /**17. 电话号码的字母组合
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     * 回溯：路径：已经映射好的数组部分
     * 选择列表：当前字符对应的所有字母映射
     * 终止条件：digits映射到了最后一位
     * */
    Map<Character,Character[]> map=new HashMap<>();
    List<String> res=new LinkedList<>();
    void backtrack(String digits,int index,StringBuffer path){
        if (index==digits.length()){
            res.add(new String(path));
            return;
        }

        //做出选择
        char cur = digits.charAt(index);
        Character[] characters = map.get(cur);
        for (Character ch:characters) {
            path.append(ch);
            backtrack(digits,index+1,path);
            path.delete(index,index+1);

        }
    }

    public List<String> letterCombinations(String digits) {
        if (digits.length()==0) return res;
        map.put('2',new Character[]{'a','b','c'});
        map.put('3',new Character[]{'d','e','f'});
        map.put('4',new Character[]{'g','h','i'});
        map.put('5',new Character[]{'j','k','l'});
        map.put('6',new Character[]{'m','n','o'});
        map.put('7',new Character[]{'p','q','r','s'});
        map.put('8',new Character[]{'t','u','v'});
        map.put('9',new Character[]{'w','x','y','z'});
        backtrack(digits,0,new StringBuffer());
        return res;
    }
}
